#include <iostream>
#include <list>
#include <utility>
#include <unordered_map>

using std::cout;
using std::endl;
using std::list;
using std::pair;
using std::unordered_map;

class LRU
{
public:
    LRU(size_t capa)
    : _capacity(capa)
    {

    }

    //将<key, value>插入到list中
    void put(int key, int value)
    {
        //查看key值是不是存在的
        auto it = _cache.find(key);
        //1、如果存在
        if(it != _cache.end())
        {
            //修改list中的节点的value值
            it->second->second = value;//注意更新key对应的value
            //将元素移动到list的首部
            _nodes.splice(_nodes.begin(), _nodes, it->second);
        }
        //2、不存在
        else
        {
            //看list中元素是不是已经满了
            //2.1、如果满了
            if(_capacity == _nodes.size())
            {
                //获取最后一个元素（目的就是找到其中的key值，
                //这样才能从unordered_map中进行删除）
                auto deleteNode = _nodes.back();//注意这三行代码的前后关系
                //删除最后一个元素，然后将新的<key, value>插入到最前面
                _nodes.pop_back();
                //元素还要从unordered_map中删除
                _cache.erase(deleteNode.first);
            }
            //2.2、如果不满
            _nodes.push_front({key, value});//注意：这两行代码在if与else中都要写
            _cache[key] = _nodes.begin();//所以就没有写else，也没有写两次
        }
    }

    int get(int key)
    {
        //需要判断元素是不是存在的
        auto it = _cache.find(key);
        //1、元素不存在
        if(it == _cache.end())
        {
            return -1;
        }
        //2、元素存在
        else
        {
            //置换位置
            _nodes.splice(_nodes.begin(), _nodes, it->second);
            return it->second->second;//注意：返回满足条件的值之前，要进行置换
        }
    }

    void print() const//注意：辅助查看元素在put与get之后的结果是不是对的
    {
        for(auto &elem : _nodes)
        {
            cout << "(" << elem.first
                 << ", " << elem.second 
                 << ") ";
        }
        cout << endl;
    }
private:
    size_t _capacity;//存放元素的个数（容量）
    list<pair<int, int>> _nodes;//存放数据的数据结构
    //存放key以及key在list中的迭代器的位置
    unordered_map<int, list<pair<int, int>>::iterator> _cache;
};

void test()
{
    LRU lru(3);

    cout << endl;
    lru.put(1, 10);//(1, 10)
    lru.print();

    cout << endl;
    lru.put(2, 20);//(2, 20) (1, 10)
    lru.print();

    cout << endl;
    cout << "lru.get(1) = " << lru.get(1) << endl;//10
    lru.print();

    cout << endl;
    lru.put(3, 30);//(3, 30) (1, 10) (2, 20)
    lru.print();

    cout << endl;
    lru.put(4, 40);//(4, 40) (3, 30) (1, 10)
    lru.print();

    cout << endl;
    cout << "lru.get(2) = " << lru.get(2) << endl;//-1
    lru.print();

    cout << endl;
    lru.put(3, 33);
    lru.print();

    cout << endl;
    cout << "lru.get(1) = " << lru.get(1) << endl;//10
    lru.print();
}

int main(int argc, char *argv[])
{
    test();
    return 0;
}


